﻿// 0729train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <string>
#include <queue>

using namespace std;


/*
 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
 输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]

 */

void solve01(vector<int>& temperatures)
{
    //右边第一个比curr_name大的数，两数坐标相减
    vector<int>oh_vec = temperatures;
    int oh_vec_size = oh_vec.size();

    stack<int>oh_stack;
    vector<int>result_vec(oh_vec_size);

    //for (int i =0; i< oh_vec_size - 1; i++)
    for (int i = oh_vec_size-1; i>=0; i--)
    {
        int curr_num = oh_vec[i];
	    while (!oh_stack.empty() && oh_vec[oh_stack.top()]<=curr_num)
	    {
            oh_stack.pop();
	    }

        if (!oh_stack.empty())
        {
            result_vec[i] = oh_stack.top()-i;
        }
        else
        {
            result_vec[i] = 0;
        }
        oh_stack.push(i);
    }

    for (auto &item:result_vec)
    {
        cout << item << ' ';
    }

    //solve01
    //------
}


/*
接雨水
https://leetcode.cn/problems/trapping-rain-water/description/
 */


void ComputedArea(vector<int>&height)
{
    stack<int>oh_stack;
    vector<int>oh_vec = height;

    int result = 0;
    for (int i = 0; i < oh_vec.size(); i++)
    {
        int curr_h = oh_vec[i];
        
        if (oh_stack.empty())
        {
            oh_stack.push(i);
        }
        else if (oh_vec[oh_stack.top()] > curr_h)
        {
            oh_stack.push(i);
        }
        else if (oh_vec[oh_stack.top()] == curr_h)
        {
            oh_stack.push(i);
        }
        else //stack_top<curr_h
        {
            while (!oh_stack.empty() && oh_vec[oh_stack.top()] < curr_h)
            {
                int bottom_index = oh_stack.top();
                int bottom_h = oh_vec[bottom_index];
                oh_stack.pop();

                if (!oh_stack.empty())
                {
                    int left_index = oh_stack.top();
                    int left_h = oh_vec[left_index]; //左边
                    int area_h = min(left_h, curr_h) - bottom_h;
                    int curr_index = i;
                    int area_w = curr_index - left_index - 1;

                    int area = area_w * area_h;
                    result += area;
                }

            }
            oh_stack.push(i);

        }
        //for------
    }

    cout << result;

    //ComputedArea
    //------
}


/*
 请你仅使用两个栈实现先入先出队列。
队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x)将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty()如果队列为空，返回 True ；否则，返回 False

 */

class MyQueue {
public:
    MyQueue() {

    }

    stack<int>cache_stack;
    stack<int>main_stack;

    void push(int x) {
        main_stack.push(x);
    }

    int pop() {
        while (!main_stack.empty())
        {
            cache_stack.push(main_stack.top());
            main_stack.pop();
        }

        int queue_front = cache_stack.top();
        cache_stack.pop();

        while (!cache_stack.empty())
        {
            main_stack.push(cache_stack.top());
            cache_stack.pop();
        }

        return queue_front;
        //------
    }

    int peek() {
        while (!main_stack.empty())
        {
            cache_stack.push(main_stack.top());
            main_stack.pop();
        }

        int queue_front = cache_stack.top();

        while (!cache_stack.empty())
        {
            main_stack.push(cache_stack.top());
            cache_stack.pop();
        }

        return queue_front;
    }

    bool empty() {
        return main_stack.empty();
    }
};


/*
 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

 */
class MyStack {
public:
    MyStack() {

    }
    queue<int>main_queue;
    queue<int>cache_queue;
    void push(int x) {
        main_queue.push(x);
    }

    int pop() {
        int back = main_queue.back();

        //这里必须用size判断，防止队列里有相同的元素
        while (main_queue.size()!=1)
        {
            cache_queue.push(main_queue.front());
            main_queue.pop();
        }
        
        main_queue.pop();

        while (!cache_queue.empty())
        {
            main_queue.push(cache_queue.front());
            cache_queue.pop();
        }
        
        return back;
    }

    int top() {
        return main_queue.back();
    }

    bool empty() {
        return main_queue.empty();
    }
};


int main()
{
	{
        //["MyStack","push","push","push","push","push","top","pop","top"]
        //[1],[2],[3],[4],[2]
        MyStack myStack;
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(2);
        cout << myStack.top() << endl; // 返回 2
        cout << myStack.pop() << endl; // 返回 2
        cout << myStack.top() << endl;

        return 0;
	}

	{
        MyQueue myQueue;
        myQueue.push(1); // queue is: [1]
        myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
        cout << myQueue.peek(); // return 1
        cout << myQueue.pop(); // return 1, queue is [2]
        cout << myQueue.empty(); // return false

        return 0;
	}


	{
        vector<int>height = { 0,1,0,2,1,0,1,3,2,1,2,1 };
        ComputedArea(height);
        return 0;
	}

    vector<int>temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
    solve01(temperatures);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
